class Solution{//5. Longest Palindromic Substring O(N^2) O(1)
public:
    string longestPalindrome(string s){
        int n=s.size();if(n<2)return s;
        int L=0, len=1;
        for(int i=0;i<n;){
            int l=i,r=i;
            while(r+1<n && s[r+1]==s[i])++r;
            i=r+1;
            while(l-1>=0 && r+1<n && s[l-1]==s[r+1]){--l;++r;}
            if(r-l+1>len){len=r-l+1;L=l;}
        }
        return s.substr(L,len);
    }
};

class Solution{//143 O(N) O(N)
public:
    void reorderList(ListNode*head){
        if(!head||!head->next)return;
        vector<ListNode*>v;
        for(auto p=head;p;p=p->next)
        v.push_back(p);
        int i=0, j=(int)v.size()-1;
        while(i<j){
            v[i++]->next=v[j];
            if(i==j)break;
            v[j--]->next=v[i];
        }
        v[i]->next=nullptr;
    }
};

class Solution{ // 876 O(N) O(1)
public:
    ListNode* middleNode(ListNode*head){
        ListNode* slow=head, *fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

class Solution{//23.O(N log k) O(k)
public:
    ListNode* mergeKLists(std::vector<ListNode*>&lists){
        struct Cmp{bool operator()(ListNode*a,ListNode*b)const{return a->val>b->val;}};
        std::priority_queue<ListNode*,std::vector<ListNode*>,Cmp>pq;
        for(size_t i=0;i<lists.size(); i++)
            if(lists[i]!=nullptr)pq.push(lists[i]);
        ListNode dummy(0);
        ListNode*tail=&dummy;
        while(!pq.empty()){
            ListNode*node=pq.top();pq.pop();
            tail->next=node;tail=node;
            if(node->next!=nullptr)pq.push(node->next);
        }
        return dummy.next;
    }
};

#include<string>
#include<vector>
#include<climits>
class Solution{ //76 O(|s| + |t|) O(1)
public:
    std::string minWindow(std::string s, std::string t){
    if(t.empty()||s.size()<t.size()) return"";
    std::vector<int>need(128,0);
    for(char c:t) ++need[c];
    int miss=(int)t.size(), bestL=0,bestLen=INT_MAX;
    for(int l=0,r=0;r<s.size();++r){
        if(--need[s[r]]>=0)--miss;
        while(miss==0){
            if(r-l+1<bestLen)bestLen=r-l+1,bestL=l;
            if(++need[s[l++]]>0)++miss;
        }
    }
    return bestLen==INT_MAX?"":s.substr(bestL,bestLen);
    }
};

class Solution{//209 O(N) O(1)
public:
    int minSubArrayLen(int target, vector<int>&nums){
        int n=nums.size(), l=0, ans=n+1, sum=0;
        for(int r=0;r<n;++r){
            if(nums[r]>=target) return 1;
            sum+=nums[r];
            while(sum>=target){
                int len=r-l+1;
                ans=std::min(ans,len);
                sum-=nums[l++];
            }
        }
        return (ans<=n)?ans:0;
    }
};

class Solution{ //239 O(N) O(N)
public:
    vector<int> maxSlidingWindow(vector<int>&a, int k){
        int n=(int)a.size();
        if(n==0||k==0) return{};
        vector<int> left(n), right(n), ans; ans.reserve(n-k+1);
        for(int i=0;i<n;++i)
            left[i]=(i%k==0)?a[i]:max(left[i-1],a[i]);
        for(int i=n-1;i>=0;--i)
            right[i]=((i+1)%k==0||i==n-1)?a[i]:max(right[i+1],a[i]);
        for(int i=0;i+k<=n;++i)
            ans.push_back(max(right[i],left[i+k-1]));
        return ans;
    }
};